A typical data communications network includes a number of host computers linked by one or more data communications devices coupled via any type of transmission media. Data is transmitted between one or more hosts on the network in the form of network packets or cells which typically have a predefined, standardized format.
In some networks, network packets are classified into different Quality of Service (QoS) classes which dictate how competing traffic flows are allocated resources which effects how quickly such packets travel from their sources to their destinations.
In such a network, data communications devices (e.g., routers and repeaters) typically receive and retransmit network packets based on the QoS classes of the packets. For example, in a network having video packets as a first QoS class and email packets (electronic mail) as a second QoS class, a network router may internally manage packets such that received video packets are retransmitted with less delay than email packets. As a result, network packet destinations (e.g., receiving hosts) generally perceive different responses, or Qualities of Service, for different QoS classes (e.g., faster video transmissions than email transmissions).
In a network which uses QoS classifications, data communications devices generally manage network packets internally according to packet management algorithms. Typically, in such a device, the algorithms provide control signals as a function of local network traffic data which has been accumulated and post-processed over an extended period of time. For example, a network router may operate in a particular manner based on local network traffic data, which has been accumulated and post-processed over several days, to enable the router to achieve QoS goals of transmitting received video packets with a maximum time delay of 100 ns and transmitting received email packets with a maximum time delay of 100 ms.
Typically, a person known as a network administrator is responsible for ensuring that a data communications device (e.g., the router) achieves its QoS goals. When the data communications device does not provide adequate QoS, the administrator analyzes the operation of the device relative to the local network traffic and attempts to improve the performance of the device to enable it to achieve its QoS goals. Furthermore, even if the device adequately achieves its QoS goals, the administrator may still attempt, on occasion, to further improve the performance of the device to enable it to more easily manage network packets and achieve its QoS goals.
When the administrator attempts to improve a data communication device""s ability to manage network packets, the administrator typically studies the network traffic passing through the particular point where the device is connected to the network. For example, the administrator may connect a network packet monitor at the input of the data communications device to classify packet sizes, to count the number of packets in total or the number of packets of a particular QoS class received by the data communications device. Often, the administrator allows the monitor to accumulate this information over an extended period of time such as several hours or perhaps several days. For example, the monitor stores the size and count information in a computer file on a computer for future analysis.
After the count information has been collected, the administrator generates particular network metrics from the count information. For example, the administrator may have logged the amount of time that elapsed while collecting the count information. Accordingly, the administrator can determine the overall packet rate provided by the data communications device by dividing the counted overall number of packets by the elapsed time. That is,       overall packet rate    =                    overall number of packets counted                    elapsed time              .  
Similarly, the rate for a particular packet type can be determined by dividing the counted number of packets for a particular QoS class by the elapsed time. That is,          packet rate for a particular
            packet type    =                    number of packets counted
 for a particular QoS class                    elapsed time              .  
In this manner, the administrator determines the characteristics of the network traffic handled by the data communications device during the elapsed time period. This information along with packet size information can help improve understanding of the resource requirements of different traffic flows.
After the administrator has determined the network traffic characteristics of the elapsed time period, the administrator examines the settings of the data communications device. In particular, the administrator verifies that the operating parameters of the data communications device are set such that the device will manage packets correctly and efficiently in the future, if the device encounters network traffic having the same characteristics. For example, if the device is already set to handle such traffic correctly and efficiently, the administrator leaves the parameters unchanged or may change the parameters slightly with the hope of improving performance. However, if the device is not set to handle such traffic correctly and efficiently, the administrator modifies the parameters such that the device will handle the traffic correctly and efficiently in the future. The size of the output queues of the data communications device and the priority of different packet types are examples of parameters that the administrator may examine and perhaps adjust.
After the administrator has determined that the data communications device is properly set to manage packets correctly and efficiently and if the data communications device encounters new network traffic having different characteristics as previously encountered during the elapsed time period, the administrator may choose to subsequently repeat the above described procedure at some time in the future. For example, the administrator may (i) monitor the network traffic several days later to accumulate new size and count information, (ii) generate new network metrics using the new information, and (iii) then examine the settings of the data communications device relative to the newly generated network metrics.
Using the above-described technique, the data communications device is tuned to manage network packets correctly and efficiently with the assistance of human intervention by the network administrator. With an aggressive approach towards fine tuning the data communications device, the administrator may repeat the adjustment process a dozen or so times over the course of a several days.
In contrast to conventional network packet management techniques, the invention is directed to techniques for managing network packets in a data communications device using a real-time feedback signal. In one technique, a traffic monitor observes network packet traffic transmitted from an output of the data communications device, and generates the real-time feedback signal based on the observed traffic. The data communications device manages newly received packets according to the real-time feedback signal, i.e., according to the relatively instantaneously observed traffic, thus enabling the data communications device to perform real-time packet management and adjust to dynamically changing conditions within the network at a rapid pace.
One embodiment involves the use of a data communications device having a memory. The data communications device transmits an initial set of packets which are monitored by a traffic monitor. The traffic monitor then provides the real-time feedback signal indicating transmission information regarding the initial or previous set of packets. The data communications device manipulates (or handles) a new set of packets within its memory based on the real-time feedback signal, and transmits the new set of packets from the data communications device based on how the new set of packets was manipulated within the memory.
Preferably, each packet belongs to one of multiple packet classes, e.g., Quality of Service (QoS) classes such as video, audio, general data and best effort classes. Classes may also be defined by packet source, destination, or any other internal data in the packet, or by other information such as a physical location (e.g., port) on the device upon which the packet arrived. As such, the real-time feedback signal indicates transmission levels of the multiple packet classes for the initial set of packets. For example, the real-time feedback signal may indicate packet counts for each packet class in the initial set, and a total count for the number of packets in the initial set.
The memory of the data communications device preferably stores a queue structure. As such, the data communications device manipulates the new set of packets by scheduling each of the new set of packets in the queue structure based on the transmission levels of the multiple packet classes for the initial set of packets, as indicated by the real-time feedback signal. Alternatively, the device manipulates the new set of packets by reordering queues of the queue structure when the transmission levels of the multiple packet classes for the initial set of packets, as indicated by the real-time feedback signal, cause the data communications device to detect a reorder condition. As another alternative, the device manipulates the new set of packets by discarding a packet of the new set of packets from the queue structure when the transmission levels of the multiple packet classes for the initial set of packets, as indicated by the real-time feedback signal, cause the data communications device to detect a discard condition. As yet another alternative, the data communications device manipulates the new set of packets by performing multiple functions using the real-time feedback signal. For example, the device schedules packets, reorders queues and discards packets, based on the real-time feedback signal. In this arrangement, information within the real-time feedback signal is preferably an input to an algorithm used by the device, as the device performs many complex calculations.
Preferably, each packet includes a bit pattern indicative of one of the multiple packet classes. The bit pattern resides in a predetermined location within each packet, i.e., within a type of service (TOS) field (e.g., indicating the QoS assigned to that packet). As such, to monitor transmission of the initial set of the packets and provide the real-time feedback, the traffic monitor preferably samples (monitors) packets from the initial set of packets. The traffic monitor recognizes, for each sampled packet, a bit pattern of that packet, and updates a set of data structures based on the recognized bit pattern of that packet, the data structures respectively corresponding to the multiple packet classes. Furthermore, the traffic monitor generates the real-time feedback signal based on the updated set of data structures such that the real-time feedback signal is indicative of the transmission levels of the multiple packet classes for the initial (or previous) set of packets.
In the TOS arrangement, the real-time feedback signal preferably indicates a bit count for each of the multiple packet classes, and a total bit count. As such, the data communications device preferably includes traffic analysis logic that provides a bit rate for each of the multiple packet classes based on the bit count for each of the multiple packet classes and the total bit count such that the new set of packets are manipulates based on the bit rate for each of the multiple packet classes.
Preferably, the data communications device can request information from the traffic monitor. In particular, the device requests the information by generating a request signal for information regarding the transmission levels of the multiple packet classes for the initial set of packets or any previous set of packets. In response, the traffic monitor generates the real-time feedback signal such that it includes the requested information.
It should be understood that network traffic patterns may shift within a relatively short period of time. As such, some conventional data communications devices may not be optimally adjusted to manage a network traffic with particular characteristics if the adjustments are infrequent or if the adjustments rely on network data gathered over extended periods of time. In contrast, the invention involves optimally adjusting how a data communications device manages packets based on a real-time feedback signal. Accordingly, if the traffic pattern shifts within a relatively short period of time, the data communications device, configured according to the invention, can adapt its operation to more optimally manage packets in a manner superior to that done in conventional data communications devices.
Additionally, the invention provides for an automated adjustment process. That is, once configured in accordance with the invention, no human intervention is required to enable the data communications device to manage packets correctly and efficiently within a network having changing network traffic characteristics. Rather, the real-time feedback signal is generated in a contiguous manner enabling the data communications device to adjust its operation dynamically and automatically.
Furthermore, unlike conventional systems which have large storage requirements to store large amounts of network data gathered over extended periods of time and large processors to analyze the network data, the invention has relatively small hardware requirements. That is, since the invention uses a real-time feedback signal that contains fresh data, there are less memory requirements and processor demands.
Also, the invention enables different types of network information to be gathered on-the-fly. That is, if the invention cannot determine how to adjust itself in view of particular network data acquired from the traffic monitor, the invention can request other types of network data to assist the invention in its determination of how to adjust itself. Accordingly, there is less likelihood that conflicting goals will result in oscillating performance. That is, the invention will tend towards a convergence or compromise between the different goals (e.g., QoS goals). Hence, a first action by the invention based on a particular goal may provide only a modest performance improvement, and a subsequent action based on a different goal may provide a substantially better improvement in a non-oscillating manner.